package com.cuz.hot100;

public class Q10regularExpressionMatch {

    public static void main(String[] args) {
        //1.   abc a*bc  ==》bc bc
        //2.   aabc a*bc ===>bc bc
        //3. aaabc a*bc===>aa a*bc
//        System.out.println(isMatch1("abc", "a*bc"));
//        System.out.println(isMatch1("aabc", "a*bc"));
//        System.out.println(isMatch1("aaabc", "a*bc"));
//        System.out.println(isMatch1("aa", "a"));
//        System.out.println(isMatch1("ab", ".*"));
        //"mississippi"
        //"mis*is*p*."
//        System.out.println(isMatch1("mississippi", "mis*is*p*."));
        System.out.println(isMatch1("aa", "a*"));
//        System.out.println("ab".charAt(0) + ".*".substring(1));
    }

    public static boolean isMatch1(String s, String p) {
        if (p.isEmpty()) {
            return s.isEmpty();
        }
        boolean isFirstCharEqual = (!s.isEmpty())
                && (p.charAt(0) == '.' || s.charAt(0) == p.charAt(0));
        if (p.length() > 1 && p.charAt(1) == '*') {
            //bc a*bc                          abc a*bc  ===>bc a*bc
            return isMatch1(s, p.substring(2)) || (isFirstCharEqual && isMatch1(s.substring(1), p));
        } else {
            return isFirstCharEqual && isMatch1(s.substring(1), p.substring(1));
        }
    }

    public static boolean isMatch2(String s, String p) {
        if (p.isEmpty()) {
            return s.isEmpty();
        }
        char[] pChars = p.toCharArray();
        char[] sChars = s.toCharArray();
        int pLen = pChars.length;
        int sLen = sChars.length;
        //dp[i-1][j-1]====>第i字符结尾和 第j字符结尾是否匹配
        boolean[][] dp = new boolean[sLen + 1][pLen + 1];
        dp[0][0] = true;
        //""  和 ？* 都是true  ？可以是任何字符
        //"" a*b*c* 也为true
        for (int index = 2; index <= pLen; index++) {
            //
            dp[0][index] = p.charAt(index - 1) == '*' && dp[0][index - 2];
        }
        for (int row = 0; row < sLen; row++) {
            for (int col = 0; col < pLen; col++) {
                //当前字符是*
                if (p.charAt(col) == '*') {
                    // aba abac* 先看aba 和 aba 是否相等  相对 那么c* 出现0此
                    dp[row + 1][col + 1] = dp[row + 1][col - 1]
                            //abaa aba*  ==> *前面的a 是否和 abaa 最后一个a相等
                            //且 aba 和 aba* 是否相等 相对那么让a复制所需要的次数
                            || (firstMatch(sChars, pChars, row, col - 1) && dp[row][col + 1]);
                } else {
                    dp[row + 1][col + 1] = firstMatch(sChars, pChars, row, col) && dp[row][col];
                }
            }
        }
        return dp[pLen][sLen];
    }

    private static boolean firstMatch(char[] s, char[] p, int i, int j) {
        return s[i] == p[j] || p[j] == '.';
    }

}
